//
//  124. 二叉树中的最大路径和.swift
//  LeetCodeTrain
//
//  Created by rjb on 2021/5/31.
//  Copyright © 2021 rjb. All rights reserved.
//

import Foundation
class Solution124 {
    // 求最大路径和实际上是求左子树的最大路径和与右子树的路径和
    // 二叉树的最大路径和
    // 左和，右和，左+中+右的和
    // 特别注意节点是有负数的
    var result: Int = Int.min
    func maxPathSum(_ root: TreeNode?) -> Int {
        treePathSum(root)
        return result
    }
    @discardableResult
    func treePathSum(_ node: TreeNode?) -> Int {
        guard let node = node else {
            return 0
        }
        let leftSum = treePathSum(node.left)
        let rightSum = treePathSum(node.right)
        let rootSum = max(leftSum + node.val, rightSum + node.val,node.val)
        result = max(result, rootSum, leftSum + rightSum + node.val)
        return rootSum
    }
    
    static func test() {
        let root: TreeNode? = createNode()
        let solution = Solution124()
        let result = solution.maxPathSum(root)
        print(result)
    }
    static func createNode () -> TreeNode? {
        let node1 = TreeNode(1)
        let node2 = TreeNode(2)
        let node3 = TreeNode(2)
        let node4 = TreeNode(3)
        let node5 = TreeNode(4)
        let node6 = TreeNode(4)
        let node7 = TreeNode(3)
        
        node1.left = node2
        node1.right = node3
        node2.left = node4
        node2.right = node5
        node3.left = node6
        node3.right = node7
        return node1
    }
}
